#include "BuildingPlacer.h"

#define MAX(a,b) ((a > b) ? a:b)
#define MIN(a,b) ((a < b) ? a:b)

bool VitalZone::containsPoint(Position point, int skip)
{
	Point<int,1> p = point;
	int counter = ((skip == 0) ? 1:0);
	int icounter = counter;
	int i;
	int N = polygon.size();

	if(N < 1)
		return false;
	else if(N == 1)
		return (point == polygon[0]);

	double xinters;
	Point<int,1> p1,p2;

	p1 = polygon[icounter];
	for (i=icounter+1; i <= N; i++) {
		if(i == skip)
			continue;
		p2 = polygon[((i==N) ? icounter:i)];
		if (p.y > MIN(p1.y,p2.y)) {
			if (p.y <= MAX(p1.y,p2.y)) {
				if (p.x <= MAX(p1.x,p2.x)) {
					if (p1.y != p2.y) {
						xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
						if (p1.x == p2.x || p.x <= xinters)
							counter++;
					}
				}
			}
		}
		p1 = p2;
	}

	if((counter - icounter) % 2 == 0)
		return false;
	return true;
}

// a structure designed to sort polygons into a container of points in clockwise order
struct PolyPoint {
	Position point;
	double theta; // Both theta and r should be set to their correct
	double r;     // value for polar coords before the sort begins
	bool operator > (PolyPoint& rhs)
	{
		return (theta > rhs.theta); // sort by acending order
	}
};

void insertion_sort(std::vector<PolyPoint>& x)
{
	PolyPoint key;
	int i;
	for(int j=1;j<x.size();j++)
	{
		key=x[j];
		i=j-1;
		while(i>=0 && x[i]>key)
		{
			x[i+1]=x[i];
			i--;
		}
		x[i+1]=key;
	}
}

void VitalZone::addPoint(Position point)
{
	// we don't want any intereior points
	if(containsPoint(point))
		return;

	static std::vector<PolyPoint> sPoints;
	sPoints.clear();

	polygon.insert(polygon.end(), point);

	// calculate temporary fake centroid for the first three points added
	// this is just the average point value as a real centroid is not needed
	// all other points added after the first three will use the last
	// calculated real centroid for converting to polar form.
	double cx=0., cy=0.;
	for(int i=0; i < polygon.size(); i++) {
		cx += (double)polygon[i].x;
		cy += (double)polygon[i].y;
	}
	cx /= (double)polygon.size();
	cy /= (double)polygon.size();
	centroid.x = (int)cx;
	centroid.y = (int)cy;

	//////////////////////////////////////////////////////////////////////
	// sort the polygon so points apear in clockwize order
	// place them in an unsorted container of polar points
	for(int i=0; i < polygon.size(); i++) {
		PolyPoint sPoint;
		sPoint.point = polygon[i];

		// convert to polar coords where (0,0) = centroid
		double y = (double)sPoint.point.y - (double)centroid.y;
		double x = (double)sPoint.point.x - (double)centroid.x;
		sPoint.theta = atan2(y, x);
		sPoint.r = sqrt(x*x + y*y);
		sPoints.insert(sPoints.end(), sPoint);
	}
	
	// as this is run for every point added insertion sort is optimal
	// sort them based off of theta
	insertion_sort(sPoints);
	
	// all tied theta values may be in the wrong order for r causing
	// jagged corners and overlaps so they should be sorted based off
	// of r. Decending order if rb >= re, and Acending order if rb < re
	// where rb := the r value of the point before the ties and
	// where re := the r value of the point after the ties.

	/*int rbi = 0, rei;
	for(int n=0; n < sPoints.size()-1; n++) {
		//static double rb, re;
		if(sPoints[n].theta == sPoints[n+1].theta) {
			if(rbi == 0) { // this is the begining of a tie
				rbi = n - 1;
			}
		}
		else {             // this is the end of a tie
			rei = n + 1;
			double rb, re;
			// if sPoints[rbi] D.N.E. then loop around to back.
			if(rbi < 0)
				rb = sPoints[sPoints.size() - 1].r;
			else
				rb = sPoints[rbi].r;

			// if sPoints[rbe] D.N.E. then loop from the front.
			if(rei >= sPoints.size())
				re = sPoints[0].r;
			else
				re = sPoints[rei].r;

			// sort group of ties based off of r from rbi to rei
			// uses a slightly modified insertion sort
			
			bool decending = (rb >= re);
			PolyPoint key;
			int i;
			for(int j= 1+rbi; j < rei+1; j++)
			{
				key=sPoints[j];
				i=j-1;
				while(i >= 0 && ((sPoints[i].r < key.r && decending) || (sPoints[i].r > key.r && !decending)))
				{
					sPoints[i+1]=sPoints[i];
					i--;
				}
				sPoints[i+1]=key;
			}
			rbi = 0; // set rbi back to 0 after handling this tied group
		}
	}*/
	// copy sorted polar form back into polygon
	polygon.clear();
	for(int n=0; n < sPoints.size(); n++)
		polygon.insert(polygon.end(), sPoints[n].point);

	////////////////////////////////////////////////////
	// Remove interior points
	// Loop through all points and see if polygon skipping
	// said point has said point as an interior point.
	if(polygon.size() > 3) {
		int j = 0;
		for(std::vector<Position>::iterator i = polygon.begin(); i != polygon.end(); i++) {
			if(containsPoint(*i, j))
				polygon.erase(i);
			else
				j++;
		}
	}

	////////////////////////////////////////////////////
	// Calculate the real centroid
	double signedArea = 0.0;
    double x0 = 0.0; // Current vertex X
    double y0 = 0.0; // Current vertex Y
    double x1 = 0.0; // Next vertex X
    double y1 = 0.0; // Next vertex Y
    double a = 0.0;  // Partial signed area

    // For all polygon except last
    int i=0;
	for (i=0; i<polygon.size()-1; ++i)
    {
        x0 = polygon[i].x;
        y0 = polygon[i].y;
        x1 = polygon[i+1].x;
        y1 = polygon[i+1].y;
        a = x0*y1 - x1*y0;
        signedArea += a;
        cx += (x0 + x1)*a;
        cy += (y0 + y1)*a;
    }

    // Do last vertex
    x0 = polygon[i].x;
    y0 = polygon[i].y;
    x1 = polygon[0].x;
    y1 = polygon[0].y;
    a = x0*y1 - x1*y0;
    signedArea += a;
    cx += (x0 + x1)*a;
    cy += (y0 + y1)*a;

    signedArea *= 0.5;
    cx /= (6.*signedArea);
    cy /= (6.*signedArea);

	// truncate the values to match bwapi positions
	centroid.x = (int)cx;
	centroid.y = (int)cy;

	//////////////////////////////////////////////////////////////////////
	// Calculate new area
	area = 0.;
	int j=polygon.size()-1;

	for (int i=0; i<polygon.size(); i++) {
		double jx = polygon[j].x;
		double jy = polygon[j].y;
		double ix = polygon[i].x;
		double iy = polygon[i].y;

		area+=(jx+ix)*(jy-iy);
		j=i;
	}
}

Position VitalZone::closestPoint(Position point)
{
	Position minPoint;
	double minDist = -1.;

	double x1 = point.x;
	double y1 = point.y;
	double x2,y2;

	for(int i = 0; i < polygon.size(); i++) {
		x2 = polygon[i].x;
		y2 = polygon[i].y;
		if(double dist=(x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2) < minDist || minDist < 0.) {
			minDist = dist;
			minPoint = polygon[i];
		}
	}

	return minPoint;
}
